/**
 * url： https://101.zoo.team/zi-fu-chuan/zi-fu-chuan-part-3-yan-zheng-hui-wen-zi-fu-chuan-shi-xian-strstr-zui-chang-gong-gong-qian-zhui-he-zu#zui-chang-gong-gong-qian-zhui
 * 
 * 编写一个函数来查找字符串数组中的最长公共前缀
 * 
 * 示例
 * 输入：["flower","flow","flight"]
 * 输出："fl"
 * 
 */

/**
 * 递归迭代
 * 
 * 1. 查找前 n-1 个字符串的最长公共前缀m
 * 2. 查找 m 与最后一个字符串的公共前缀
 * 
 * longestCommonPrefix([S1, S2,...,Sn]) = findCommPrefix(longestCommonPrefix([S1, S2,...,Sn-1]), Sn)
 * 
 */

const longestCommonPrefix1 = (arr) => {
    
    function findCommPrefix (arrA, arrB) {
        let i = 0;
        while (i < arrA.length && i < arrB.length && arrA.charAt(i) === arrB.charAt(i)) {
            i++;
        }
        return i > 0 ? arrA.substring(0, i) : '';
    }
    
    if (arr.length > 0) {
        let commonPrefix = arr[0]
        for (let i = 1 ; i < arr.length ;i++) {
            commonPrefix = findCommPrefix(commonPrefix, arr[i])
        }
        return commonPrefix;
    }
    
    return ''
}


/**
 * 循环迭代
 */

const longestCommonPrefix2 = (arr) => {
    if (arr.length === 0) {
        return ''
    }
    
    let i = 0;
    let flag = true;
    
    while (flag) {
        if (strs[0].length > 1) {
            const charA = strs[0].charAt(i);
            
            for (let j = 1 ; j < strs.length ; j++) {
                if (strs[j].length <= i || strs[j].charAt(i) !== charA) {
                    flag = false;
                    break;
                }
            }
            
        } else {
            flag = false
        }
        
        i++; 
    }
    return strs[0].substring(0, i - 1);
}
